class Node(object):
    def __init__(self, elem=-1,lchild=None,rchild=None):
        self.elem = elem
        self.lchild = lchild
        self.rchild = rchild

class BinaryTree(object):
    def __init__(self):
        self.root = None
        self.help_queue=[]
    def level_build_tree(self, node:Node):#建树
        if self.root is None:
            self.root = node
            self.help_queue.append(node)
        else:
            self.help_queue.append(node)
            if self.help_queue[0].lchild is None:#如果当前结点左孩子为空
                self.help_queue[0].lchild = node#放入左孩子
            else:
                self.help_queue[0].rchild = node#放入右孩子
                self.help_queue.pop(0)
    def pre_order(self, current_node:Node):#前序遍历,根左右
        if current_node:
            print(current_node.elem, end=" ")
            self.pre_order(current_node.lchild)
            self.pre_order(current_node.rchild)
    def end_order(self, current_node:Node):#后序遍历，左右根
        if current_node:
            self.end_order(current_node.lchild)
            self.end_order(current_node.rchild)
            print(current_node.elem, end=" ")
    def middle_order(self, current_node:Node):#中序遍历，左根右
        if current_node:
            self.middle_order(current_node.lchild)
            print(current_node.elem, end=" ")
            self.middle_order(current_node.rchild)
    def level_order(self, current_node:Node):#层次遍历
        help_queue = []
        help_queue.append(self.root)#树根入队
        while help_queue:
            current_node = help_queue.pop(0)
            print(current_node.elem, end=" ")
            if current_node.lchild:
                help_queue.append(current_node.lchild)
            if current_node.rchild:
                help_queue.append(current_node.rchild)


if __name__  == "__main__":
    tree = BinaryTree()
    for i in range(1,11):
        new_node = Node(i)#实例化结点
        tree.level_build_tree(new_node)#把结点放进树
    tree.pre_order(tree.root)
    print()
    tree.end_order(tree.root)
    print()
    tree.middle_order(tree.root)
    print()
    tree.level_order(tree.root)